翻訳と辞書
Words near each other
・ Quiero llenarme de ti
・ Quiero Más
・ Quiero Ser
・ Quiero ser (I want to be ...)
・ Quiero Ser (song)
・ Quiero Ser Feliz
・ Quiero ser tu dueño
・ Quiero Television
・ Quiero Verte Más
・ Quiers
・ Quiers-sur-Bézonde
・ Quierschied
・ Quierzy
・ Quiesce
・ Quiescence
Quiescence search
・ Quiestède
・ QUIET
・ Quiet
・ Quiet & Still
・ Quiet (album)
・ Quiet (EP)
・ Quiet American
・ Quiet American (horse)
・ Quiet as a Nun
・ Quiet as It's Kept
・ Quiet Birdmen
・ Quiet Bliss
・ Quiet Cave
・ Quiet Chaos (film)


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Quiescence search : ウィキペディア英語版
Quiescence search

Quiescence search is an algorithm typically used to evaluate minimax game trees in game-playing computer programs. It is a remedy for the horizon problem faced by AI engines for various games like chess and Go.
==The horizon effect==
(詳細はartificial intelligence where, in many games, the number of possible states or positions is immense and computers can only search a small portion of it, typically a few ply down the game tree. Thus, for a computer searching only five ply, there is a possibility that it could make a move that would prove to be detrimental later on (say, after six moves), but it cannot see the consequences because it cannot search far into the tree. Consider this chess position with black to move:〔(ChessBase.com - Chess News - Bilbao – the humans strike back )〕
Here White is down a pawn in material, and a good move for black would be 39... Qxg3+ 40. Kxg3 f5. However, Fritz chooses the suboptimal move 39... Bc2??. This move lets White force many of Black's moves, but Fritz doesn't care because it appears to be able to win more material along the way. White responds with 40. Qxh4 and Black resigns after 40. ... gxh4 41. Rc1 Rxb3? 42. Nxb3 Bxb3 43. a5 Nc4 44. b5 Ba4 45. bxa6 Bc6 46. a7 Kg7 47. a6 Ba8 48. Rb1.
This problem occurs because computers only search a certain number of moves ahead. Human players usually have enough intuition to decide whether to abandon a bad-looking move, or search a promising move to a great depth. A quiescence search attempts to emulate this behavior by instructing a computer to search "interesting" positions to a greater depth than "quiet" ones (hence its name) to make sure there are no hidden traps and, usually equivalently, to get a better estimate of its value.
Any sensible criterion may be used to distinguish "quiet" moves from "noisy" moves; high activity (high movement on a chess board, extensive capturing in Go, for example) is commonly used for board games. As the main motive of quiescence search is usually to get a good value out of a poor evaluation function, it may also make sense to detect wide fluctuations in values returned by a simple heuristic evaluator over several ply. Modern chess engines may search certain moves up to 2 or 3 times deeper than the minimum. In highly "unstable" games like Go and reversi, a rather large proportion of computer time may be spent on quiescence searching.
This pseudocode illustrates the concept in an algorithmic manner:
function quiescence_search(''node'', ''depth'')
if ''node'' appears quiet or ''node'' is a terminal node or ''depth'' = 0
return estimated value of ''node''
else
//One might use minimax or alpha-beta search here...
search children of ''node'' using recursive applications of quiescence_search
return estimated value of children

//...and here
function normal_search(''node'', ''depth'')
if ''node'' is a terminal node
return estimated value of ''node''
else if ''depth'' = 0
if ''node'' appears quiet
return estimated value of ''node''
else
return estimated value from quiescence_search(''node'', reasonable_depth_value)
else
search children of node using recursive applications of normal_search
return estimated value of children

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Quiescence search」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.